package learn.sort.marge;

import learn.CommUtil;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 归并排序
 */
public class MargeSort {

    public static void main(String[] args) {
        int[] arr = CommUtil.arr(120);
        int[] old = Arrays.copyOf(arr, arr.length);
//        int[] arr = {69, 26};
        CommUtil.printArray("原数组: ", arr);
        process(arr, 0, arr.length - 1);
        CommUtil.printArray("排序后: ", arr);

        Arrays.sort(old);
        CommUtil.check(old, arr);
    }

    /**
     * 归并排序
     * 分而治之,把原数组分为2个partition,2个partition又分为4partition,直到有序开始合并,并保证新的partition有序,从上向下分,从下向上合并
     * 最终得到有序数组
     * @param arr
     * @param l
     * @param r
     */
    public static void process(int[] arr, int l, int r) {
        if (l == r) {
            return;
        }
        int m = l + ((r - l) >> 1);
        //1.左边递归继续分
        process(arr, l, m);
        //2.右边递归继续分
        process(arr, m + 1, r);
        //3.把两个有序的partition合并到一个partition
        marge(arr, l, m, r);

    }

    private static void marge(int[] arr, int l, int m, int r) {

        int[] help = new int[r - l + 1];
        int l1 = l;
        int l2 = m + 1;
        int i = 0;
        //合并到help数组
        while (l1 <= m && l2 <= r) {
            help[i++] = arr[l1] <= arr[l2] ? arr[l1++] : arr[l2++];
        }
        while (l1 <= m) {
            help[i++] = arr[l1++];
        }
        while (l2 <= r) {
            help[i++] = arr[l2++];
        }
        // 修改原数组
        for (i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }

    }


}


